package examination_practice01;


import javax.naming.PartialResultException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Activity{
    public int start;
    public int endTime ;
    public Activity(int start,int endTime){
        this.start=start;
        this.endTime=endTime;
    }
}
public class SelectActivity {
    //贪心算法实现活动安排问题
    public static List<Activity> selectActivity(Activity[] activities){
        //收容活动集合
        List<Activity> selectActivity=new ArrayList<>();
        //先排序，按照从结束时间从小到大排
        Arrays.sort(activities,(activity1,activity2)->
                Integer.compare(activity1.endTime,activity2.endTime));

        //将第一个activities数组元素加入到集合中
        selectActivity.add(activities[0]);
        //定义初始比较值
        int prevoiusEndTime=activities[0].endTime;
        for (int i=1;i<activities.length;i++){
            if (activities[i].start>=prevoiusEndTime){
                selectActivity.add(activities[i]);
                prevoiusEndTime=activities[i].endTime;//更新结束时间
            } else if (activities[i].endTime<prevoiusEndTime) {
                selectActivity.remove(i-1);
                selectActivity.add(activities[i]);
                prevoiusEndTime=activities[i].endTime;
            }
        }
        return selectActivity;
    }
    public static void main(String[] args){
        Activity[] activities={new Activity(0,4),
                new Activity(0,2),
                new Activity(2,4),
                new Activity(4,7),
                new Activity(4,6),
                new Activity(6,10),
                new Activity(6,8),
                new Activity(10,13),
                new Activity(8,13),
                new Activity(8,10)
        };
        List<Activity> selectActivity=selectActivity(activities);
        System.out.println("收容的活动最大集合为：");
        for (Activity activity:selectActivity){
            System.out.println("("+activity.start+","+activity.endTime+")");
        }
    }

}
